package leetcode101.search_problem.dfs;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code5
 * @Description 77. Combinations
 * Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].
 *
 * You may return the answer in any order.
 *
 * Example 1:
 *
 * Input: n = 4, k = 2
 * Output:
 * [
 *   [2,4],
 *   [3,4],
 *   [2,3],
 *   [1,2],
 *   [1,3],
 *   [1,4],
 * ]
 * Example 2:
 *
 * Input: n = 1, k = 1
 * Output: [[1]]
 *
 * Constraints:
 *
 * 1 <= n <= 20
 * 1 <= k <= n
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-01 10:14
 */
public class Code5 {
    public static void main(String[] args) {
        System.out.println(combine(4, 2).toString());
    }

    public static List<List<Integer>> res;

//    public static List<List<Integer>> combine(int n, int k) {
//        res = new ArrayList<>();
//        int[] comb = new int[k];
//        dfs(comb, 0,1, n, k);
//        return res;
//    }
//
//
//    public static void dfs(int[] comb, int count, int pos, int n, int k) {
//        /*
//        comb代表组合结果
//        count代表组合中数字的个数
//        pos代表当前位置的数字
//        n代表总数
//        k代表范围
//         */
//        if (count == k) {
//            List<Integer> temp = new ArrayList<>();
//            for (int i = 0; i < comb.length; i++) {
//                temp.add(comb[i]);
//            }
//            res.add(temp);
//            return;
//        }
//
//        for (int i = pos; i <= n; i++) {
//            comb[count++] = i;
//            dfs(comb, count, i + 1, n, k);
//            count--;
//        }
//    }

    public static List<List<Integer>> combine(int n, int k) {
        int[] combination  = new int[k];
        res = new ArrayList<>();
        dfs(combination, 0, 1, n, k);
        return res;
    }

    public static void dfs(int[] combination, int count, int pos, int n, int k) {
        if (count == k) {
            List<Integer> temp = new ArrayList<>();
            for (int i : combination) {
                temp.add(i);
            }
            res.add(temp);
            return;
        }

        for (int i = pos; i <= n; i++) {
            combination[count++] = i;
            dfs(combination, count, i + 1, n, k);
            count--;
        }
    }



}
